# -*- coding: utf-8 -*-


"""

http://iregex.org/blog/trie-in-python.html
out
 (?-xism:foo(?:ba[hr]|xar|zap?))
 
Trie in Python
August 1st, 2010 Categories: 笔记

关于 Trie 的介绍，请读上文Trie，此不赘述。本文主要
分析 Trie 实现原理，并给出 Python 的实现。


构造检索树

先正更上文不精确之处。上文说，

具体说来，就是提取出备选项文本的公共部分，构造“检索树”…

其实 Trie 并不是提取所有的“公共部分”，而是
只提取“前缀”而已。例如，对于正则式/abbcc|abcc/，
它生成的结果是(?-xism:ab(?:bcc|cc))，
而非abb?cc，可见它并没有智能到足够程度，
可应用之而不可迷信之。

具体原因，可以通过读源码以及本文分析而理解。

新建一个 Trie 对象之后，每向它添加一个字串，它都做如下操作：

整体的数据结构是 Hash 表，亦即Python中的Dictionary。

Hash表的每一个元素指向它自身；以所输入的子串的每个字母
为Key，如果它自身为空，则指向一个新建的匿名Hash；

最后一个元素的Key为空字串‘’，value为1。这也是判断每个
分支是否结束的标志。
请看一下对于字串 foobar分析后所生成的数据结构：

{
'f' => {
         'o' => {
                  'o' => {
                           'b' => {
                                    'a' => {
                                             'r' => {
                                                      '' => 1
                                                    }
                                           }
                                  }
                         }
                }
       }
}
很美观，对不对。奇妙的是，对于第一条字串，
它生成的结构是这样的；对于新插入的第二条，
第三条……第N条字串，它不是另起炉炉灶，
而是萧规曹随，见缝插针，充分利用前面已经成生的数据结构。

这要归功于Hash/Dictionary这种数据结构的特点。
看一下针对于foobar foobah fooxar foozap 
fooza 完全插入后的效果：


  'f' => {
           'o' => {
                    'o' => {
                             'b' => {
                                      'a' => {
                                               'h' => {
                                                        '' => 1
                                                      },
                                               'r' => {
                                                        '' => 1
                                                      }
                                             }
                                    },
                             'x' => {
                                      'a' => {
                                               'r' => {
                                                        '' => 1
                                                      }
                                             }
                                    },
                             'z' => {
                                      'a' => {
                                               '' => 1,
                                               'p' => {
                                                        '' => 1
                                                      }
                                             }
                                    }
                           }
                  }
         }
}
这个结构图很直观地解释了
为什么是提取前缀而非后缀中缀什么的。

构造一个检索树，已经不是一个问题。现在
来看看如何将它转换为正则表达式。

检索树的正则表现

原文源码比较精炼，用了许多Perl特有的语法且
无注释。我简要解释一下作者思路。

如果当前节点的 key 为空，且当前只有一个键，
则该分支结束，返回空值。这也是前文伏笔的照应：

为什么要加上$ref->{''}=1;。

对于不为空的节点，一一分析之。
只要当前节点不为空，一直递归调用本函数，
将当前key+下个节点的递归结果push到数组@alt中备用。


否则只将 key push到 @cc中。
@cc是用来保存单个字母的，而@alt则是用来保存多个字母的备选项的。
将@cc中的元素格式化为[abc]的样子。当然，如果只有一个元素就不必了。
将@alt中的元素格式化为(?:abc|xyz)的样子，
一个元素则免。

在适当的地方添加问号，表示备选。


读懂了源码，自己实现起来就不是问题了。

我在读此代码时，使用了纸笔抄写、观测
print、Data::Dumper输出等方式来辅助理解。

事实证明卓有成效。

移植到Python

从Perl到Python，其实就像从英语到法语的转换一样
，只是将拼写方式，细微语法修整一下即可，算不得伤筋
动骨的大手术。我是用它来验证理解、熟悉语法细节的。


代码如下。只要from trie import Trie就能使用了。


Ubuntu 10.04, Python 2.6.5 环境下测试通过。

Tags: perl, python, trie


"""

#!/usr/bin/python


#
#author:         rex
#blog:           http://iregex.org
#filename        tr.py
#created:        2010-08-01 20:24

class Trie():
    """Regexp::Trie in python"""
    def __init__(self):
        self.data={}

    def add(self, word):
        ref=self.data
        for char in word:
            ref[char]=ref.has_key(char) and ref[char] or {}
            ref=ref[char]
        ref['']=1

    def dump(self):
        return self.data

    def _regexp(self, pData):
        data=pData
        if data.has_key("") and len(data.keys())==1: 
            return None

        alt=[]
        cc=[]
        q=0
        for char in sorted(data.keys()):
            if isinstance(data[char],dict):
                try:
                    recurse=self._regexp(data[char])
                    alt.append(char+recurse)
                except:
                    cc.append(char)
            else:
                q=1
        cconly=len(alt) and 0 or 1  #if len, 0; else:0

        if len(cc)>0:
            if len(cc)==1:
                alt.append(cc[0])
            else:
                alt.append('['+''.join(cc)+']')

        if len(alt)==1:
            result=alt[0]
        else:
            result="(?:"+"|".join(alt)+")"

        if q:
            if cconly:
                result+="?"
            else:
                result="(?:%s)?" % result
        return result 
    def regexp(self):
        return "(?-xism:%s)" % self._regexp(self.dump())

a=Trie()

for w in ['foobar', 'foobah', 'fooxar', 'foozap', 'fooza']:
    a.add(w)
print a.regexp()

